package dfs;

public class ZeroOneMatrix542 {
    public int[][] updateMatrix(int[][] matrix) {
        if(matrix.length == 0)
            return null;
        for(int i = 0; i< matrix.length;i++){
            for(int j = 0; j < matrix[0].length; j++){
                matrix[i][j] = dfs(matrix,i,j,0);
            }
        }
        return matrix;
    }
    public int dfs(int[][] matrix, int i, int j, int dist){
        if(i < 0 || i >= matrix.length || j < 0 || j >= matrix[0].length)
            return Integer.MAX_VALUE;
        if(matrix[i][j] == 0)
            return dist;

        int up = dfs(matrix,i - 1,j,dist + 1);
        int down = dfs(matrix,i+1,j,dist + 1);
        int left = dfs(matrix,i,j-1,dist + 1);
        int right = dfs(matrix,i, j+1,dist + 1);
        return Math.min(Math.min(up,down),Math.min(left,right));
    }

    public static void main(String[] args) {
//        return new ZeroOneMatrix542().updateMatrix();
    }
}
